package _11_整理题目._9_高频题目;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * 
 * 思路：
 * 扫描两轮，先从左往右，再从右往左
 * 从左往右：
 * 遇到比当前的值 小的，统计当前小桶里的水，继续移动；
 * 遇到比当前的值 大的，累计小桶里的水 到 sum。
 * 如果没有比当前大的，则不统计
 * 
 */
public class _03_盛接雨水 {
    
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
    
    public long maxWater (int[] arr) {
        if(arr==null || arr.length==0) return 0;
    
        int cur=0, tmp=0, sum=0;
        for(int i=0; i<=arr.length-1; i++) {
            if(arr[cur] > arr[i]) {
                tmp += arr[cur] - arr[i];
            } else {
                sum += tmp;
                tmp = 0;
                cur = i;
            }
        }
    
        cur = arr.length-1;
        tmp = 0;
        for(int j=arr.length-1; j>=0; j--) {
            if(arr[cur] > arr[j]) {
                tmp += arr[cur] - arr[j];
            } else if(arr[cur] < arr[j]) {
                sum += tmp;
                tmp = 0;
                cur = j;
            }
        }
    
        return sum;
    }
    
    @Test
    public void main() {
        int[] input = {4,2,0,3,2,5};
        assert maxWater(input)==9;
        assert trap(input)==9;
    }
}
